1. Field of the Invention
This invention relates in general to graphical computer systems, and in particular, to a layout method for arc-dominated labelled graphs.
2. Description of Related Art
Arc-dominated graphs are those that contain most of the visible information in their arc labels. An example of such graphs is a finite state machine (FSM) of the Mealy machine variety, which is used extensively in telecommunication protocol design and recent object-oriented computer-assisted software engineering (CASE) tools. Also, in object-oriented analysis and design, it often becomes necessary to draw object-relationship diagrams to depict different usage scenarios. Each diagram typically has a few objects, but there could be a large number of relationships between them.
Currently known layout methods typically give preference to the placement of graph nodes, and are therefore generally not suitable for laying out arc-dominated graphs. For example, these methods tend to avoid laying out arcs which cross nodes, and instead route arcs around the nodes in order to minimize arc cross-overs. However, such methods allow arcs to cross each other. Thus, when used to lay out arc dominated labelled graphs, these prior art methods result in graphs in which arc-labels overlap, making the visible information in the graphs hard to decipher.
In contrast, with arc-dominated graphs, suitable separation between two arcs is an important layout criterion. In these cases, the respective arc labels, which could be rather long strings, should not overlap any arc, node or other label. Thus, there is a need in the art for a layout method for arc-dominated labelled graphs that meets the layout criterion of such graphs.